<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>438. 找到字符串中所有字母异位词</title>
  </head>
  <body>
    <script>
      //       给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

      // 异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

      //

      // 示例 1:

      // 输入: s = "cbaebabacd", p = "abc"
      // 输出: [0,6]
      // 解释:
      // 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
      // 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
      //  示例 2:

      // 输入: s = "abab", p = "ab"
      // 输出: [0,1,2]
      // 解释:
      // 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
      // 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
      // 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
      //

      // 提示:

      // 1 <= s.length, p.length <= 3 * 104
      // s 和 p 仅包含小写字母

      // 来源：力扣（LeetCode）
      // 链接：https://leetcode.cn/problems/find-all-anagrams-in-a-string
      // 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
      /**
       * @param {string} s
       * @param {string} p
       * @return {number[]}
       */
      var findAnagrams = function (s, p) {
        let p2 = p.split('').sort().join('')
        const windowLen = p.length
        let i = 0,
          j = i + windowLen
        let res = []
        debugger
        while (j <= s.length) {
          let str = s.slice(i, j)
          // if (str === p) {
          //   i++
          //   j++
          //   continue
          // }
          // let test = str.split('').sort().join('')
          if (str.split('').sort().join('') === p2) {
            res.push(i)
          }
          i++
          j++
        }
        return res
      }

      // var findAnagrams = function (s, p) {
      //   let sL = s.length,
      //     pL = p.length
      //   if (sL < pL) return []

      //   let left = 0,
      //     right = 0, // 滑动窗口两侧索引
      //     windowMap = new Map(), // 统计滑动窗口内每个 char 的数量
      //     pMap = new Map(), // 统计字符串 p 内每个 char 的数量
      //     valid = 0, // 滑动窗口 和 字符串 p 中数量相等的 char 的个数
      //     ret = [] // 结果集

      //   for (const char of p) {
      //     // pMap.set(char, pMap.has(char) ? pMap.get(char) + 1 : 0)
      //     pMap.set(char, (pMap.get(char) || 0) + 1)
      //   }

      //   while (right < sL) {
      //     let char = s[right++]
      //     if (pMap.has(char)) {
      //       windowMap.set(char, windowMap.has(char) ? windowMap.get(char) + 1 : 0)
      //       windowMap.get(char) === pMap.get(char) && valid++
      //     }

      //     if (right - left === pL) {
      //       // 滑动窗口内的字符数和 pL 相等时，并且 2 个 map 中每个 char 的数量都相等，说明找到异位词了。
      //       valid === pMap.size && ret.push(left)

      //       // 无论有没有找到异位词，left 都要右移了。
      //       let char = s[left++]
      //       if (pMap.has(char)) {
      //         // 如果 pMap 中有 char，并且 pMap 中 char 的数量和 windowMap 中的相等，（因为 left 要右移了，所以）valid--，
      //         windowMap.get(char) === pMap.get(char) && valid--
      //         // 因为 left 要右移了，所以 windowMap 中的 char 数量也 - 1，
      //         windowMap.set(char, windowMap.get(char) - 1)
      //       }
      //     }
      //   }
      //   return ret
      // }

      console.log(findAnagrams('abab', 'ab'))
    </script>
  </body>
</html>
